package 中等.滑动窗口;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 * <p>
 * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
 */
public class 找到字符串中所有字母异位词_438 {

    public static void main(String[] args) {

        System.out.println(findAnagrams("baa", "aa"));

    }

    /**
     * 滑动窗口
     * 每次滑动其实变化的只有2个字符，所以维护，窗口中不同的字符个数就行
     * 每次滑动，进来的字符个数+1，出去的字符个数-1
     *
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();

        if (s.length() < p.length()) {
            return list;
        }
        //只有小写字母
        int[] sletters = new int[26];
        int[] pletters = new int[26];
        for (int i = 0; i < p.length(); i++) {
            sletters[s.charAt(i) - 'a']++;
            sletters[p.charAt(i) - 'a']--;
        }
        if (Arrays.equals(sletters, pletters)) {
            list.add(0);
        }

        //窗口宽度
        int width = p.length() - 1;
        for (int i = 1; i <= s.length() - p.length(); i++) {
            //滑动窗口
            sletters[s.charAt(i - 1) - 'a']--;
            sletters[s.charAt(i + width) - 'a']++;
            if (Arrays.equals(sletters, pletters)) {
                list.add(i);
            }
        }
        return list;
    }

}
